package com.example.rwq_test.niuke.list;

/**
 * 链表区间翻转
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/10/17
 */
public class ReverseBetween {

    /**
     * @param head ListNode类
     * @param m    int整型
     * @param n    int整型
     * @return ListNode类
     */
    //
    //说明：方便理解，以下注释中将用left，right分别代替m,n节点
    public static ListNode reverseBetween2 (ListNode head, int m, int n) {
        // write code here
        if (m == n) {
            return head;
        }
        int index = 1;
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;

        while (index < m) {
            pre = pre.next;
            index++;
        }

        ListNode cur = pre.next;
        while (index < n) {
            ListNode nextNode = cur.next;
            cur.next = nextNode.next;
            nextNode.next = pre.next;
            pre.next = nextNode;
            index++;
        }

        return dummyNode.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        ListNode listNode = reverseBetween(listNode1, 1, 3);

        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    public static ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if (m == n) {
            return head;
        }

        ListNode temp = null;
        ListNode cur = head;
        int idx = 1;

        while (idx < m) {
            temp = cur;
            cur = cur.next;
            idx++;
        }

        ListNode pre = null;
        while (idx <= n) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            idx++;
        }
        if (temp == null) {
            // 说明m=1,从一开始就进行倒序了，这时pre就是头结点，head已经是尾节点了，但cur还可能是有值的，需要将cur接到head后面，然后返回pre;
            head.next = cur;
            return pre;
        }
        // 这时m!=1, 需要将cur续接上，那应该续接到哪那？应该续接到temp.next.next上。
        temp.next.next = cur;
        temp.next = pre;

        return head;
    }



}
